package cn.edu.nju.ws.sview.reasoning.schema;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;

import cn.edu.nju.ws.sview.cache.SubclassCache;
import cn.edu.nju.ws.sview.cache.URIIDCache;
import cn.edu.nju.ws.sview.reasoning.Predicate;

/**
 * Subclass reasoning
 * @author ssgong
 *
 */
public class Subclass {
   private static Subclass INSTANCE = null;
   private Subclass(){
   }
   
   public static synchronized Subclass getInstance(){
		if (INSTANCE == null) {
			INSTANCE = new Subclass();
		}
		return INSTANCE;
   }
    /**
     * given several classes , find the minimal ones of them(belong to them)
     * @param classes
     * @return may contain equivalent classes
     * @throws Throwable 
     */
   public HashSet<Integer> getMinClasses(HashSet<Integer> classes) throws Throwable{
	   HashSet<Integer> result = new HashSet<Integer>();
	   HashMap<Integer, HashSet<Integer>> graph = new HashMap<Integer, HashSet<Integer>>();
	   for(Integer classID:classes){
		   HashSet<Integer> superSet = SubclassCache.getInstance().getSuperClass(classID) ;
		   superSet.retainAll(classes) ;
		   graph.put(classID,superSet) ;
	   }
		HashMap<Integer, HashSet<Integer>> reverseGraph = new HashMap<Integer, HashSet<Integer>>();
		ArrayList<Integer> finish = new ArrayList<Integer>();
		HashSet<Integer> visited = new HashSet<Integer>();
		for(Integer shit :classes){
			if(!visited.contains(shit)){
			   firstDFS(shit,finish, graph,reverseGraph, visited);
			}
		}
		HashMap<Integer,HashSet<Integer>> scc = new HashMap<Integer,HashSet<Integer>>();
		visited.clear();
		for (int i = finish.size() - 1; i >= 0; i--) {
			Integer classID= finish.get(i);
			if (!visited.contains(classID)){
				HashSet<Integer> set = secondDFS(classID, reverseGraph,  visited);
				for(Integer s:set){
					scc.put(s, set) ;
				}
			}
		}
	   for(Integer element:classes){
		   HashSet<Integer> set = scc.get(element) ;
 		   if(!reverseGraph.containsKey(element)){
			   result.add(element) ;
		   }else {
			   if(!result.contains(element)){
				   HashSet<Integer> shit = new HashSet<Integer>();
				   for(Integer member:set){
					   if(reverseGraph.containsKey(member)){
						   shit.addAll(reverseGraph.get(member)) ;
					   }
				   }
				   if(set.containsAll(shit)){
					   result.addAll(set) ;
				   }
			   }
		   }
	   }
	   return result;
   }
   
   /**
    * get the top order of classes . That is the subclass is at front
    * @param classes
    * @return 
 * @throws Throwable 
    */
   public ArrayList<HashSet<Integer>> getTopOrder(HashSet<Integer> classes) throws Throwable{
	   ArrayList<HashSet<Integer>> result = new  ArrayList<HashSet<Integer>>();
	   HashMap<Integer, HashSet<Integer>> graph = new HashMap<Integer, HashSet<Integer>>();
	   for(Integer classID:classes){
		   HashSet<Integer> superSet = SubclassCache.getInstance().getSuperClass(classID) ;
		   superSet.retainAll(classes) ;
		   graph.put(classID,superSet) ;
	   }
		HashMap<Integer, HashSet<Integer>> reverseGraph = new HashMap<Integer, HashSet<Integer>>();
		ArrayList<Integer> finish = new ArrayList<Integer>();
		HashSet<Integer> visited = new HashSet<Integer>();
		for(Integer shit :classes){
			if(!visited.contains(shit)){
			   firstDFS(shit,finish, graph,reverseGraph, visited);
			}
		}
		visited.clear();
		for (int i = finish.size() - 1; i >= 0; i--) {
			Integer classID= finish.get(i);
			if (!visited.contains(classID)){
				HashSet<Integer> set =secondDFS(classID, reverseGraph, visited);
				result.add(set) ;
			}
		}
	   return result;
   }
   
   /**
    * given several classes , find the minimal superclasses of them
    * @param classes
    * @return may contain equivalent classes
 * @throws Throwable 
    */
   public HashSet<Integer> getMinimalSuperClasses(HashSet<Integer> classes) throws Throwable{
	   HashSet<Integer> superclasses = new HashSet<Integer>();
	   for(Integer element:classes){
		   HashSet<Integer> set = SubclassCache.getInstance().getSuperClass(element) ;
		   set.add(element) ;
		   if(superclasses.size()>0){
			   superclasses.retainAll(set) ;
		   }else{
			   superclasses.addAll(set) ;
		   }
	   }
	   return getMinClasses(superclasses) ;
   }
   
   
	public void firstDFS(Integer start,ArrayList<Integer> finish, HashMap<Integer, HashSet<Integer>> graph,
			HashMap<Integer, HashSet<Integer>> reverseGraph,
			HashSet<Integer> visited) {
		visited.add(start);
		Iterator<Integer> itor = graph.get(start).iterator();
		while (itor.hasNext()) {
			Integer  neighbor = itor.next();
			addEdge(reverseGraph, neighbor, start);
			if (!visited.contains(neighbor))
				firstDFS(neighbor,finish, graph,reverseGraph, visited);
		}
		finish.add(start);
	}

	public HashSet<Integer> secondDFS(Integer element,
			final HashMap<Integer, HashSet<Integer>> reverseGraph,
			HashSet<Integer> visited) {
		HashSet<Integer> result = new HashSet<Integer>();
		visited.add(element);
		if (reverseGraph.get(element) == null) {
			result.add(element) ;
			return result;
		}
		Iterator<Integer> itor = reverseGraph.get(element).iterator();
		while (itor.hasNext()) {
			Integer neighbour = itor.next();
			if (!visited.contains(neighbour)){
				HashSet<Integer> set = secondDFS(neighbour, reverseGraph,  visited);
				result.addAll(set) ;
			}
		}
		result.add(element);
		return result;
	}
	
	private void addEdge(HashMap<Integer, HashSet<Integer>> reverseGraph,
			Integer source, Integer obj) {
		if (!reverseGraph.containsKey(source)) {
			HashSet<Integer> list = new HashSet<Integer>();
			list.add(obj);
			reverseGraph.put(source, list);
		} else {
			HashSet<Integer> list = reverseGraph.get(source);
			list.add(obj);
		}
		return;
	}
	
}
